package tree.tree2.symmetry.BinarySearchTree.ModifyAndConstruct;

import tree.TreeNode;

/**
 * @ClassName DeleteNode
 * @Description TODO
 * @Author lenovo
 * @Date 2023-05-11 9:59
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class DeleteNode {
    /**
     *  450. 删除二叉搜索树中的节点
     给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

     一般来说，删除节点可分为两个步骤：

     首先找到需要删除的节点；
     如果找到了，删除它。


     示例 1:



     输入：root = [5,3,6,2,4,null,7], key = 3
     输出：[5,4,6,2,null,null,7]
     解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
     一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
     另一个正确答案是 [5,2,6,null,4,null,7]。


                   6
     *     2
     *  1     4
     *
                   6
     *     2
     *  1     4
     *     3
     *
     *
                   6
     *     2
     *  1     3
     *           5
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {

       if(root.val>key){
           root.left = deleteNode(root.left,key);
       }else if(root.val<key){
           root.right = deleteNode(root.right,key);
       }else{
           if(root.left == null)return root.right;
           if(root.right == null)return root.left;
           TreeNode tempNode = root.right;
           while (tempNode.left!=null){
               tempNode = tempNode.left;
           }
           root.val = tempNode.val;
           deleteNode(root.right,tempNode.val);
       }
       return root;
    }

    public static void main(String[] args) {
        DeleteNode deleteNode = new DeleteNode();

        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left = new TreeNode(1);
        System.out.println(deleteNode.deleteNode(root, 2));
    }
}